// https://leetcode.cn/problems/kth-largest-element-in-a-stream/description/

// 算法思路总结：
// 1. 最小堆维护数据流中的第K大元素
// 2. 堆大小保持为K，堆顶即为第K大元素
// 3. 初始化时构建大小为K的最小堆
// 4. 添加新元素时，维护堆大小不超过K
// 5. 时间复杂度：O(nlogk)，空间复杂度：O(k)

#include <iostream>
using namespace std;

#include <vector>
#include <queue>
#include <algorithm>

class KthLargest 
{
public:
    KthLargest(int k, vector<int>& nums) 
    {
        _k = k;
        for (const int& num : nums)
        {
            minHeap.push(num);
            if (minHeap.size() > _k) minHeap.pop();
        }
    }
    
    int add(int val) 
    {
        minHeap.push(val);
        if (minHeap.size() > _k) minHeap.pop();
        return minHeap.top();
    }
private:
    priority_queue<int,vector<int>, greater<int>> minHeap;
    int _k;
};

int main()
{
    int k = 3; vector<int> nums = {4, 5, 8, 2};
    KthLargest* obj = new KthLargest(k, nums);

    int obj1 = obj->add(3);
    int obj2 = obj->add(5);
    int obj3 = obj->add(10);
    int obj4 = obj->add(9);
    int obj5 = obj->add(4);

    cout << obj1 << " ";
    cout << obj2 << " ";
    cout << obj3 << " ";
    cout << obj4 << " ";
    cout << obj5 << " ";
    cout << endl;

    return 0;
}